package leetcode;

import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-30 00:11
 **/
public class LeetCode23 {

    //优先队列
    class Status implements Comparable<Status> {

        int value;
        ListNode node;

        public Status(int value, ListNode node) {
            this.value = value;
            this.node = node;
        }

        @Override
        public int compareTo(Status o) {
            return value - o.value;
        }
    }

    PriorityQueue<Status> queue = new PriorityQueue<>();

    //优先队列法
    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode list : lists) {
            if (list != null) {
                queue.offer(new Status(list.val, list));
            }
        }

        ListNode tou = new ListNode();
        ListNode tail = tou;
        while (!queue.isEmpty()) {
            Status poll = queue.poll();
            tail.next = poll.node;
            tail = tail.next;
            if (poll.node.next != null) {
                queue.offer(new Status(poll.node.next.val, poll.node.next));
            }
        }
        return tou.next;
    }

    //分治法合并
    /*public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        return split(lists, 0, k - 1);
    }

    ListNode split(ListNode[] lists, int start, int end) {
        if (lists == null || start > end) {
            return null;
        }
        if (start == end) {
            return lists[start];
        }
        int avg = start + end >> 1;
        ListNode node1 = split(lists, start, avg);
        ListNode node2 = split(lists, avg + 1, end);
        return mergeTwoList(node1, node2);
    }

    ListNode mergeTwoList(ListNode node1, ListNode node2) {
        ListNode tou = new ListNode();
        ListNode tail = tou;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {

                tail.next = node1;
                node1 = node1.next;
                tail = tail.next;
            } else {
                tail.next = node2;
                node2 = node2.next;
                tail = tail.next;
            }
        }



        if (node1 != null) {
            tail.next = node1;
            node1 = node1.next;
            tail = tail.next;
        }
        if (node2 != null) {
            tail.next = node2;
            node2 = node2.next;
            tail = tail.next;
        }
        return tou.next;
    }*/

}
